package backend;

import java.util.ArrayList;

public class Dijkstra {
    
    private WeightedGraph graph;
    private MapNode start;
    private MapNode ziel;
    private ArrayList<MapNode> knoten;
    private ArrayList<Double> abstand;
    private ArrayList<MapNode> vorgaenger;  
    private ArrayList<MapNode> path = new ArrayList<MapNode>();
    
    /**Konstruktor und Initialisator
     * 
     * @param g Graph
     * @param s Start
     * @param z Ziel
     */
    public Dijkstra(WeightedGraph g, MapNode s, MapNode z ){
        this.graph = g;
        this.start = s;
        this.ziel = z;
        this.knoten = new ArrayList<MapNode>(g.getKnoten());
        this.abstand = new ArrayList<Double>();
        this.vorgaenger = new ArrayList<MapNode>();
        for (int i = 0; i < this.knoten.size(); i++){
            MapNode k = this.knoten.get(i);
            if (k == this.start) this.abstand.add(i, (double) 0);
            else this.abstand.add(i, Double.POSITIVE_INFINITY);
            this.vorgaenger.add(i, null);
        }
    }  
    
    /**Eigentlich Dijkstra-Algorithmus
     * 
     * @return kuerzester Weg (Liste von nodes)
     */
    public ArrayList<MapNode> findPath(boolean shortest){
        while (this.knoten.size() > 0){
            MapNode u = this.knotenMinimum();
            this.knoten.remove(u);
            if (u == this.ziel) break;
            for (MapNode v: this.graph.getNeighbours(u)){
                if (this.knoten.contains(v)) this.distUpdate(u, v, shortest);
            }
        }
        ArrayList<MapNode> weg = new ArrayList<MapNode>();
        MapNode u = this.ziel;
        weg.add(u);
        while (this.vorgaenger.get(this.graph.getKnoten().indexOf(u)) != null){
            u = this.vorgaenger.get(this.graph.getKnoten().indexOf(u));
            weg.add(0, u);
        }
        this.path = weg;
        return this.path;
    }
    
    /**
     * 
     * @return den Knoten mit dem kleinsten Abstand
     */
    private MapNode knotenMinimum(){
        int r = 0;
        for (int i = 1; i < this.knoten.size(); i++){
            if (this.abstand.get(this.graph.getKnoten().indexOf(this.knoten.get(i))) < this.abstand.get(this.graph.getKnoten().indexOf(this.knoten.get(r)))){
                r = i;
            }
        }
        return this.knoten.get(r);
    }
    
    /** Berechnet den Abstand von Knoten neu
     * 
     * @param u Node1
     * @param v Node2
     */
    private void distUpdate(MapNode u, MapNode v, boolean shortest){
        int index = this.graph.getKnoten().indexOf(u);
        double alternative;
        if (shortest){
            alternative = this.abstand.get(index) + this.graph.getLengthByNodes(u, v);
        }
        else {
            alternative = this.abstand.get(index) + this.graph.getTimeByNodes(u, v);
        }
        if (alternative < this.abstand.get(this.graph.getKnoten().indexOf(v))){
            this.abstand.set(this.graph.getKnoten().indexOf(v), alternative);
            this.vorgaenger.set(this.graph.getKnoten().indexOf(v), u);
        }
    }
}  